package class07;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Code05_IPO {
	public static class Node {
		public int p;
		public int c;

		public Node(int p, int c) {
			this.p = p;
			this.c = c;
		}
	}

	// 小根堆组织逻辑
	public static class MinCostComparator implements Comparator<Node> {

		@Override
		public int compare(Node o1, Node o2) {
			return o1.c - o2.c;
		}

	}

	// 大根堆组织逻辑
	public static class MaxProfitComparator implements Comparator<Node> {

		@Override
		public int compare(Node o1, Node o2) {
			return o2.p - o1.p;
		}

	}


	// k 最多做几个项目  W 初始资金 Profits 利润 Capital 花费的资金
	public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
		Node[] nodes = new Node[Profits.length];
		for (int i = 0; i < Profits.length; i++) {
			nodes[i] = new Node(Profits[i], Capital[i]);
		}

		PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());
		PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
		// 所有项目扔到被锁池中，即花费组织的小根堆
		for (int i = 0; i < nodes.length; i++) {
			minCostQ.add(nodes[i]);
		}
		for (int i = 0; i < k; i++) { // 进行k轮   k是串行能做的最多的项目数
			// 能力所及的项目，全解锁
			while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) { // 小根堆不为空，并且小根堆的花费小于现在的资金
				maxProfitQ.add(minCostQ.poll());
			}
			if (maxProfitQ.isEmpty()) {
				return W;
			}
			W += maxProfitQ.poll().p;
		}
		return W;
	}

}


/**todo：
 * 如何用对数器去检验正确性？
 *
 *
 * 所有项目都有了，从所有项目中取出4个，做一个全排列，计算出花费
 *
 *
 *
 *
 *
 */